#include "graph.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include "LinkedQueue.h"
/*
    Get_v_index：在 g 这个图中 查找顶点为v 的下标

    成功：返回下标
    失败：返回-1
*/
int Get_v_index(Graph*g, VType v)
{
    for(int i = 0; i < g->v_num; i++)
    {
        if(g->V[i] == v)
        {
            return i;
        }
    }

    return -1;
}
/*
    Create_input_Graph: 从键盘上获取图的信息数据创建一个图

    返回值：
        返回图的地址
*/
Graph* Create_input_Graph()
{
    //1.创建图:设置初值为 空图
    Graph*g = malloc(sizeof(*g));
    if(g == NULL)
        return NULL;
    g->arc_num = 0;
    g->v_num = 0;// 空图

    //获取数据
    //2.1 获取顶点数据并存储
    printf("请输入顶点个数\n");
    int num;
    scanf("%d", &num);
    getchar();//吸收\n
    if(num <= 0)
    {
        printf("顶点个数有误，空图返回\n");
        return g;
    }
    g->v_num = num;
    printf("请输入顶点：\n");
    printf("eg: ABCDE\n");
    for(int i = 0; i < g->v_num; i++)
    {
        scanf("%c", &g->V[i]);
    }
    
    //2.2 获取关系之前，先将关系数组设置为 ：无关系
    for(int i = 0; i < g->v_num; i++)
    {
        for(int j = 0; j < g->v_num; j++)
        {
            g->R[i][j] = INT32_MAX;
        }
    }
    //2.3获取关系数据并存储
    getchar();//吸收刚刚输入顶点后留下的\n
    printf("请输入相应的关系：起点 终点 权值\n");// AB3
    printf("eg : AB3\n");
    while(1)
    {
        VType start,stop;
        WType w;
    
        scanf("%c%c%d", &start, &stop, &w);
        if(start == '#')
            break;
        getchar();
        int start_index = Get_v_index(g,start);
        int stop_index = Get_v_index(g,stop);
        //printf("start:%c %d\n",start, start_index);
        //printf("stop:%c %d\n",stop,stop_index);
        g->R[start_index][stop_index] = w;
        g->arc_num++;

    }


    return g;

}

/*
    Print_Graph: 输出图 种数据信息 
*/
void Print_Graph(Graph* g)
{
    if(g == NULL)
        return ;
    printf("==============================\n");
    printf("v_num:%d arc_num = %d\n", g->v_num, g->arc_num);

    for(int i = 0; i < g->v_num; i++)
    {
        printf("%c ", g->V[i]);
    }
    printf("\n");

    for(int i = 0; i < g->v_num; i++)
    {
        for(int j = 0; j < g->v_num; j++)
        {
            if(g->R[i][j] == INT32_MAX)
                printf("~ ");
            else
                printf("%d ",g->R[i][j]);
        }
        printf("\n");
    }

}


int visited[MAX] = {0};
/*
    find_next_v:在图g中从列下标为start的位置查找下标为v的顶点的邻接点
    
    返回值：
        成功  返回找到的邻接点的下标
        失败  返回-1
*/
int find_next_v(Graph*g, int V, int start)
{
    for(int i = start; i < g->v_num; i++)
    {
        if(g->R[V][i] != INT32_MAX)
            return i;
    }
    return -1;
}
/*
    DFS : 以下标v_index为顶点在图g中做深度优先搜索
*/
void DFS(int v_index, Graph*g)
{
    //1. 访问 下标为v_index的顶点,并标记
    printf("%c ", g->V[v_index]);
    visited[v_index] = 1;

    //2. 重复不断查找v_index的邻接点全部访问完毕
    //i: 所找到的邻接点的下标
    for(int i = find_next_v(g, v_index, 0); i >=0 ; i = find_next_v(g, v_index, i+1))
    {
        if(!visited[i])
        {
            DFS(i, g);
        }
            
    }
		
		
}

void DFS_travel(Graph* g)
{
    if(g == NULL)
        return ;
    printf("DFS_travel:");
    // 对标记数组进行初值设置 ：设置为未访问
    for(int i = 0; i < g->v_num; i++)
    {
        visited[i] = 0;
    }

    //对每一个顶点进行判断是否能进行深度优先搜素
    for(int i = 0; i < g->v_num; i++)
    {
        if(visited[i] == 0)
        {
            //以下标为i的顶点为起点做深度优先搜索
            DFS(i, g);
        }
    }
    printf("\n");
}
void BFS_travel(Graph*g)
{
    if(g == NULL)
        return ;
    printf("BFS_travel:");
    //1.对标记数组进行初值设置 ：设置为未访问
    for(int i = 0; i < g->v_num; i++)
    {
        visited[i] = 0;
    }
    //2. 创建队列
    struct LinkedQueue*q = InitQueue();
    if(q == NULL)
        return;

    //3. 每一个顶点都当做起点做一下广度优先搜索
    for(int i = 0; i < g->v_num; i++)
    {
        if(visited[i] == 0)
        {
            //以i为下标的顶点做广度优先搜索
            //访问，并将以i为下标的顶点入队 （入顶点的下标）
            printf("%c ", g->V[i]);
            visited[i] = 1;
            EnQueue(q, i);
            
            while(!QueueIsEmpty(q))
            {
                //出队
                QElemType j;//存储出队元素 ： （出队元素是顶点的下标）
                DeQueue(q, &j);
                
                //出队元素的邻接点入队 ： 出队下标所代表的顶点的邻接点
                for(int k = find_next_v(g, j, 0); k >=0 ; k = find_next_v(g, j, k+1))
                {
                    if(!visited[k])
                    {
                        printf("%c ", g->V[k]);
                        visited[k] = 1;
                        EnQueue(q, k);
                    } 
                }
                
            }
        }
    }
    
    //4. 销毁队列
    DestroyQueue(q);
    
    printf("\n");
}